/**
 * 哈希查找
 * 分为两步：
 *  1：创建哈希表
 *  2：从哈希表中进行查找
 *  
 *  创建哈希表：
 *      思想：在 关键字和存储地址之间建立起映射关系函数f，可以通过 输入关键字 得到 地址
 *              函数f称为哈希函数，得到的地址表称为 哈希表
 *      冲突：不同关键字得到了同一地址的现象称为 冲突，因此产生了不同的 解决冲突的办法
 * 
 *      创建哈希函数的常用方法：（具体使用那种方法，要根据具体情况分析，选择出 产生冲突最少 的哈希函数）
 *          - 直接哈希函数
 *          - 数字分析法
 *          - 平方取中法
 *          - 折叠法
 *          - 除留取余法 （选不大于表长的质数）
 *          - 随机数法
 *      
 *      解决冲突的方法：
 *          - 开放地址法
 *          - 再哈希法
 *          - 链地址法
 *          - 公共溢出区法
 * 
 *  查找哈希表：
 *      输入关键字，然后通过 对应的哈希函数 找到对应的地址，
 *      如果对应地址没有数据，则返回失败
 *      否则对比数据，相同，返回成功，否则 通过对应的处理冲突的方法 获取下一个地址，进行比对
 *      重复上一步的步骤，直到找到返回成功，或者 地址数据为空，返回失败
 * 
 *  对于字符建立哈希表时，可以采用字符的 ASCII 码进行操作
 */

const studentList = require('./hashData')

 /**
  * 根据数据的特征，选择产生冲突最小的哈希函数，我这里采用了 直接哈希法
  * @param {} id 关键字
  */
function hash (id) {
    return id - 2019000
}

/**
 * 哈希函数
 * 采用 线性探测再散列
 * @param {*} addr 地址
 * @param {*} times 探测次数
 * @param {*} length 表长
 */
function handleConflict (addr, times, length) {
    return (addr + times)%length
}

/**
 * 创建哈希表
 * @param {} data 数据列表
 */
function createHashTable (data) {
    const hashTable = []
    for (let item of data) {
        let addr = hash(item.id)
        let times = 0 // 探测次数
        while (hashTable[addr]) {
            times++
            addr = handleConflict(addr, times, data.length) // 解决冲突
        }
        hashTable[addr] = item
    }
    return hashTable
}

/**
 * 查找 哈希表 中的数据
 * @param {*} id key
 */
function search (data, id) {
    let addr = hash(id)
    if (data[addr]) {
        let times = 0 // 探测次数
        while (data[addr].id !== id && data[addr]) {
            times++
            addr = handleConflict(addr, times, data.length)
        }
        if (data[addr].id === id) {
            return addr
        } else {
            return -1
        }
    } else {
        return  -1
    }
}

console.log(search(createHashTable(studentList), '20191002')) 